The invention relates to the determination of a relative position of a mobile unit by comparing scans of an environment. The mobile unit involved is for example a vehicle, such as a fork lift truck or a robot vehicle.
FIG. 5 shows a mobile unit 510. The mobile unit 510 has a distance sensor 520, a memory 530 and also a processing unit 540. The distance sensor 520 might for example be a laser scanner or an ultrasound sensor. Comparable technologies are likewise possible.
The scans of an environment of the mobile unit 510 recorded by the distance sensor 520 are stored in the memory 530 and processed by the processing unit 540.
The characteristics of scans and methods of scan matching described below are well known to the person skilled in the art and in particular can also be found in the publication by Gutmann, Jens-Steffen entitled ‘Robuste Navigation autonomer mobiler systems, Dissertationen for künstlichen Intelligenz’ (robust navigation of autonomous mobile systems, dissertations on artificial intelligence), Volume 241, Berlin: Akademische Verlagsgesellschaft Aka GmbH, 2000, page 21-88.
FIG. 1 shows two scans 110, 120. As is known from the related art mentioned, a scan is a geometrical two-dimensional or three-dimensional image of the environment of the mobile unit 510. The scan generally has a set of measured values which are specified as polar coordinates for example. In this case the individual measured values are referred to as scan points. The scan points can be converted into absolute Cartesian coordinates. This type of representation in Cartesian coordinates is shown in FIG. 1 for the scans 110 and 120. Pillars 130 and walls 140 respectively can be recognized in the scans 110, 120.
Scan matching means rotating and moving a scan so that a maximum overlap with for example a second scan is produced. In the case shown in FIG. 1, the scan 120 has had to be rotated slightly in a clockwise direction to obtain a maximum overlap with the scan 110.
After the rotation and movement of scan 120 has been determined, a relative position can thus be deduced which describes the relative position and orientation of the mobile unit 510 at the time of the scan 120 in relation to the time of the scan 110. In this way a local orientation for the mobile unit 510 can be enabled by ongoing scan matching.
FIG. 2 shows a processing of scans according to the related art. Within the context of scan matching undertaken here, a first scan 1 can be subjected to a comparison 12 with a second scan 2. The comparison 12 is made in this case using a known scan matching method. From the comparison 12 a relative position of the mobile unit 510 at the time of the second scan 2 in relation to the position at the time of the first scan 1 is determined. In practice this means a change of location and orientation. Subsequently the second scan 2 is subjected to a comparison 23 with a subsequent scan 3. In this case a relative position of the mobile unit 510 at the time of the subsequent scan 3 in relation to the position at the time of the second scan 2 is determined. In the same way comparisons 34, 45 of the subsequent scans 3, 4, 5 are undertaken. This method is very imprecise, since errors are accumulated with each comparison.
Because of these imprecisions wheel sensors are normally used in the methods known from the related art as a basis for determining the relative position, in order to determine a speed of the mobile unit 510 from wheel revolutions per unit of time and also an angular speed of the mobile unit 510 from a different speed of the wheels on the left and right. As an alternative or in addition an infrastructure is often used, which might for example have recourse to GPS satellites, reflective strips or magnets for determining the relative position. Furthermore a map is frequently used with which the current sensor measurements are reconciled.
Further methods are known from the related art, which use this information as a basis for determining the relative position of a mobile unit by comparing scans of the environment. Such methods for determining a relative position always require additional information from other sensors however, such as an odometry, which will be qualitatively improved by the relevant method.
The relative movements calculated from scan matching are also used in the related art to improve the accuracy of wheel-based odometry for example.
The disadvantage of the methods given is the fact that wheel sensors are expensive, if for example they have to be retrofitted, and that alternatives such as infrastructure or map data are often not available at all or only available for some of the time. Furthermore the known methods are frequently too imprecise. With scan matching in particular too many errors are accumulated. Although methods are known which can minimize the errors in the scan matching these methods have quadratic complexity, which means that they can only be used for orientation offline, not while the mobile unit is moving.